<template><div><h2 id="试除法求约数" tabindex="-1"><a class="header-anchor" href="#试除法求约数"><span>试除法求约数</span></a></h2>
<h3 id="题目" tabindex="-1"><a class="header-anchor" href="#题目"><span>题目</span></a></h3>
<p><img src="@source/notes/基础算法/4.数学知识/2-1-1.png" alt="图片加载失败"></p>
<div class="language-c++ line-numbers-mode" data-highlighter="shiki" data-ext="c++" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#ABB2BF">输入样例：</span></span>
<span class="line"><span style="color:#D19A66">2</span></span>
<span class="line"><span style="color:#D19A66">6</span></span>
<span class="line"><span style="color:#D19A66">8</span></span>
<span class="line"><span style="color:#ABB2BF">输出样例：</span></span>
<span class="line"><span style="color:#D19A66">1</span><span style="color:#D19A66"> 2</span><span style="color:#D19A66"> 3</span><span style="color:#D19A66"> 6</span><span style="color:#ABB2BF"> </span></span>
<span class="line"><span style="color:#D19A66">1</span><span style="color:#D19A66"> 2</span><span style="color:#D19A66"> 4</span><span style="color:#D19A66"> 8</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h3 id="思路" tabindex="-1"><a class="header-anchor" href="#思路"><span>思路</span></a></h3>
<p>什么是约数：如果一个数a除以另一个数b的余数为0，即 a%b == 0, 则b是a的约数。</p>
<p>如何求一个数x的所有约数：</p>
<p>用 x 除以 1 到 x 的所有数，如果余数是0，则把除数加到答案中。
可以优化吗？</p>
<p>如果 a / b = c···0，则一定有 a % c = b····0。所以一个数 x 的约数肯定是成对存在的，对称轴是 根号x。
因此，只需要用 x 除以 1 到 根号x 之间的数，如果余数是0，则把除数以及x / 除数加到答案中。</p>
<h3 id="参考代码" tabindex="-1"><a class="header-anchor" href="#参考代码"><span>参考代码</span></a></h3>
<div class="language-c++ line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="c++" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379">&#x3C;bits/stdc++.h></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">const</span><span style="color:#C678DD"> int</span><span style="color:#ABB2BF"> N </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#E06C75">e</span><span style="color:#D19A66">5</span><span style="color:#C678DD">+</span><span style="color:#D19A66">10</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#E5C07B"> res</span><span style="color:#ABB2BF">[N],idx;</span></span>
<span class="line"><span style="color:#C678DD">void</span><span style="color:#61AFEF"> ans</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#E06C75;font-style:italic"> m</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#ABB2BF">    idx </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">    for</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#ABB2BF">;i</span><span style="color:#C678DD">&#x3C;=</span><span style="color:#ABB2BF">m</span><span style="color:#C678DD">/</span><span style="color:#ABB2BF">i;i</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(m</span><span style="color:#C678DD">%</span><span style="color:#ABB2BF">i </span><span style="color:#C678DD">==</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#E5C07B">            res</span><span style="color:#ABB2BF">[idx</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> i;</span></span>
<span class="line"><span style="color:#C678DD">            if</span><span style="color:#ABB2BF">(i</span><span style="color:#C678DD">!=</span><span style="color:#ABB2BF">m</span><span style="color:#C678DD">/</span><span style="color:#ABB2BF">i) </span><span style="color:#E5C07B">res</span><span style="color:#ABB2BF">[idx</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">] </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> m</span><span style="color:#C678DD">/</span><span style="color:#ABB2BF">i;</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#61AFEF">    sort</span><span style="color:#ABB2BF">(res,res</span><span style="color:#C678DD">+</span><span style="color:#ABB2BF">idx);</span><span style="color:#7F848E;font-style:italic"> // 排序函数 数组首地址，首地址+排序元素长度</span></span>
<span class="line"><span style="color:#C678DD">    for</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;i</span><span style="color:#C678DD">&#x3C;</span><span style="color:#ABB2BF">idx;i</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">) cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#E5C07B">res</span><span style="color:#ABB2BF">[i]</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#98C379">" "</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">    cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> n;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">n;</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF">(n</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">        int</span><span style="color:#ABB2BF"> m;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">m;</span></span>
<span class="line"><span style="color:#61AFEF">        ans</span><span style="color:#ABB2BF">(m);</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#C678DD">    return</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div><h2 id="约数个数" tabindex="-1"><a class="header-anchor" href="#约数个数"><span>约数个数</span></a></h2>
<h3 id="题目-1" tabindex="-1"><a class="header-anchor" href="#题目-1"><span>题目</span></a></h3>
<p><img src="@source/notes/基础算法/4.数学知识/2-2-1.png" alt="图片加载失败"></p>
<div class="language-c++ line-numbers-mode" data-highlighter="shiki" data-ext="c++" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#ABB2BF">输入样例：</span></span>
<span class="line"><span style="color:#D19A66">3</span></span>
<span class="line"><span style="color:#D19A66">2</span></span>
<span class="line"><span style="color:#D19A66">6</span></span>
<span class="line"><span style="color:#D19A66">8</span></span>
<span class="line"><span style="color:#ABB2BF">输出样例：</span></span>
<span class="line"><span style="color:#D19A66">12</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h3 id="思路-1" tabindex="-1"><a class="header-anchor" href="#思路-1"><span>思路</span></a></h3>
<p>一个数的约数是由这个数的几个质因子相乘得到的。</p>
<p>例如：12 的质因子有 2，3。12的约数有：1，2，3，4，6，12。</p>
<p>约数1 是由 0 个 2， 0 个3相乘得到的。
约数2 是由 1 个 2， 0 个3相乘得到的。
约数3 是由 0 个 2， 1 个3相乘得到的。
约数4 是由 2 个 2， 0 个3相乘得到的。
约数6 是由 1 个 2， 1 个3相乘得到的。
约数12 是由 2 个 2， 1 个3相乘得到的。
12 可以分解为：2<sup>2*3</sup>1。所以2可以取 0 ~ 2个，3种取法。3可以取 0~1 个，2种取法。12的约数一共：2 * 3 = 6个。</p>
<p>也就是：把一个数N 写成：N = (p1<sup>x1</sup>)(p<sup>x2)(p3</sup>x3)…(pk^xk)，其中pi为质数。则N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)</p>
<h3 id="参考代码-1" tabindex="-1"><a class="header-anchor" href="#参考代码-1"><span>参考代码</span></a></h3>
<div class="language-c++ line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="c++" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379">&#x3C;bits/stdc++.h></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">const</span><span style="color:#C678DD"> int</span><span style="color:#ABB2BF"> M </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#E06C75">e</span><span style="color:#D19A66">9</span><span style="color:#C678DD">+</span><span style="color:#D19A66">7</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">unordered_map</span><span style="color:#C678DD">&#x3C;int</span><span style="color:#ABB2BF">,</span><span style="color:#C678DD">int></span><span style="color:#ABB2BF"> h;</span><span style="color:#7F848E;font-style:italic"> // map存储底数 指数</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> n;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">n;</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF">(n</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">        int</span><span style="color:#ABB2BF"> m;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">m;</span></span>
<span class="line"><span style="color:#C678DD">        for</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 2</span><span style="color:#ABB2BF">;i</span><span style="color:#C678DD">&#x3C;=</span><span style="color:#ABB2BF">m</span><span style="color:#C678DD">/</span><span style="color:#ABB2BF">i;i</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">           while</span><span style="color:#ABB2BF">(m</span><span style="color:#C678DD">%</span><span style="color:#ABB2BF">i</span><span style="color:#C678DD">==</span><span style="color:#D19A66">0</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#E5C07B">               h</span><span style="color:#ABB2BF">[i]</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">               m</span><span style="color:#C678DD">/=</span><span style="color:#ABB2BF">i;</span></span>
<span class="line"><span style="color:#ABB2BF">           }</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(m</span><span style="color:#C678DD">></span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">) </span><span style="color:#E5C07B">h</span><span style="color:#ABB2BF">[m]</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#C678DD">    long</span><span style="color:#C678DD"> long</span><span style="color:#ABB2BF"> res </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#ABB2BF">;</span><span style="color:#7F848E;font-style:italic"> // long long 类型防止溢出</span></span>
<span class="line"><span style="color:#C678DD">    for</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">auto</span><span style="color:#ABB2BF"> iter </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> h</span><span style="color:#ABB2BF">.</span><span style="color:#61AFEF">begin</span><span style="color:#ABB2BF">();iter</span><span style="color:#C678DD">!=</span><span style="color:#E5C07B">h</span><span style="color:#ABB2BF">.</span><span style="color:#61AFEF">end</span><span style="color:#ABB2BF">();iter</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">)</span></span>
<span class="line"><span style="color:#ABB2BF">        res </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> res</span><span style="color:#C678DD">*</span><span style="color:#ABB2BF">(</span><span style="color:#E5C07B">iter</span><span style="color:#ABB2BF">-></span><span style="color:#E06C75">second</span><span style="color:#C678DD">+</span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">)</span><span style="color:#C678DD">%</span><span style="color:#ABB2BF">M;</span></span>
<span class="line"><span style="color:#ABB2BF">    cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">res</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#C678DD">    return</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div><h2 id="约数之和" tabindex="-1"><a class="header-anchor" href="#约数之和"><span>约数之和</span></a></h2>
<h3 id="题目-2" tabindex="-1"><a class="header-anchor" href="#题目-2"><span>题目</span></a></h3>
<p><img src="@source/notes/基础算法/4.数学知识/2-3-1.png" alt="图片加载失败"></p>
<div class="language-c++ line-numbers-mode" data-highlighter="shiki" data-ext="c++" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#ABB2BF">输入样例：</span></span>
<span class="line"><span style="color:#D19A66">3</span></span>
<span class="line"><span style="color:#D19A66">2</span></span>
<span class="line"><span style="color:#D19A66">6</span></span>
<span class="line"><span style="color:#D19A66">8</span></span>
<span class="line"><span style="color:#ABB2BF">输出样例：</span></span>
<span class="line"><span style="color:#D19A66">252</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h3 id="思路-2" tabindex="-1"><a class="header-anchor" href="#思路-2"><span>思路</span></a></h3>
<p><img src="@source/notes/基础算法/4.数学知识/2-3-2.png" alt="图片加载失败">
<img src="@source/notes/基础算法/4.数学知识/2-3-3.png" alt="图片加载失败">
<img src="@source/notes/基础算法/4.数学知识/2-3-4.png" alt="图片加载失败">
<img src="@source/notes/基础算法/4.数学知识/2-3-5.png" alt="图片加载失败"></p>
<h3 id="参考代码-2" tabindex="-1"><a class="header-anchor" href="#参考代码-2"><span>参考代码</span></a></h3>
<div class="language-c++ line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="c++" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379">&#x3C;bits/stdc++.h></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">const</span><span style="color:#C678DD"> int</span><span style="color:#ABB2BF"> M </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#E06C75">e</span><span style="color:#D19A66">9</span><span style="color:#C678DD">+</span><span style="color:#D19A66">7</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">unordered_map</span><span style="color:#C678DD">&#x3C;int</span><span style="color:#ABB2BF">,</span><span style="color:#C678DD">int></span><span style="color:#ABB2BF"> h;</span><span style="color:#7F848E;font-style:italic"> // map存储底数 指数</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> n;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">n;</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF">(n</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">        int</span><span style="color:#ABB2BF"> m;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">m;</span></span>
<span class="line"><span style="color:#C678DD">        for</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">int</span><span style="color:#ABB2BF"> i </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 2</span><span style="color:#ABB2BF">;i</span><span style="color:#C678DD">&#x3C;=</span><span style="color:#ABB2BF">m</span><span style="color:#C678DD">/</span><span style="color:#ABB2BF">i;i</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">           while</span><span style="color:#ABB2BF">(m</span><span style="color:#C678DD">%</span><span style="color:#ABB2BF">i</span><span style="color:#C678DD">==</span><span style="color:#D19A66">0</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#E5C07B">               h</span><span style="color:#ABB2BF">[i]</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">               m</span><span style="color:#C678DD">/=</span><span style="color:#ABB2BF">i;</span></span>
<span class="line"><span style="color:#ABB2BF">           }</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(m</span><span style="color:#C678DD">></span><span style="color:#D19A66">1</span><span style="color:#ABB2BF">) </span><span style="color:#E5C07B">h</span><span style="color:#ABB2BF">[m]</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#C678DD">    long</span><span style="color:#C678DD"> long</span><span style="color:#ABB2BF"> res </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#ABB2BF">;</span><span style="color:#7F848E;font-style:italic"> // long long 类型防止溢出</span></span>
<span class="line"><span style="color:#C678DD">    for</span><span style="color:#ABB2BF">(</span><span style="color:#C678DD">auto</span><span style="color:#ABB2BF"> iter </span><span style="color:#C678DD">=</span><span style="color:#E5C07B"> h</span><span style="color:#ABB2BF">.</span><span style="color:#61AFEF">begin</span><span style="color:#ABB2BF">();iter</span><span style="color:#C678DD">!=</span><span style="color:#E5C07B">h</span><span style="color:#ABB2BF">.</span><span style="color:#61AFEF">end</span><span style="color:#ABB2BF">();iter</span><span style="color:#C678DD">++</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">        long</span><span style="color:#C678DD"> long</span><span style="color:#ABB2BF"> temp </span><span style="color:#C678DD">=</span><span style="color:#D19A66"> 1</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">        while</span><span style="color:#ABB2BF">(</span><span style="color:#E5C07B">iter</span><span style="color:#ABB2BF">-></span><span style="color:#E06C75">second</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">)</span></span>
<span class="line"><span style="color:#ABB2BF">            temp </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> (temp</span><span style="color:#C678DD">*</span><span style="color:#E5C07B">iter</span><span style="color:#ABB2BF">-></span><span style="color:#E06C75">first</span><span style="color:#C678DD"> +</span><span style="color:#D19A66"> 1</span><span style="color:#ABB2BF">)</span><span style="color:#C678DD">%</span><span style="color:#ABB2BF">M;</span></span>
<span class="line"><span style="color:#ABB2BF">        res</span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> res</span><span style="color:#C678DD">*</span><span style="color:#ABB2BF">temp</span><span style="color:#C678DD">%</span><span style="color:#ABB2BF">M;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#ABB2BF">    cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">res</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#C678DD">    return</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div><h2 id="最大公约数" tabindex="-1"><a class="header-anchor" href="#最大公约数"><span>最大公约数</span></a></h2>
<h3 id="题目-3" tabindex="-1"><a class="header-anchor" href="#题目-3"><span>题目</span></a></h3>
<p><img src="@source/notes/基础算法/4.数学知识/2-4-1.png" alt="图片加载失败"></p>
<div class="language-c++ line-numbers-mode" data-highlighter="shiki" data-ext="c++" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#ABB2BF">输入样例： </span></span>
<span class="line"><span style="color:#D19A66">2</span></span>
<span class="line"><span style="color:#D19A66">3</span><span style="color:#D19A66"> 6</span></span>
<span class="line"><span style="color:#D19A66">4</span><span style="color:#D19A66"> 6</span></span>
<span class="line"><span style="color:#ABB2BF">输出样例：  </span></span>
<span class="line"><span style="color:#D19A66">3</span></span>
<span class="line"><span style="color:#D19A66">2</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h3 id="思路-3" tabindex="-1"><a class="header-anchor" href="#思路-3"><span>思路</span></a></h3>
<h4 id="什么是最大公约数" tabindex="-1"><a class="header-anchor" href="#什么是最大公约数"><span>什么是最大公约数</span></a></h4>
<p>最大公约数（Greatest Common Divisor）指两个或多个整数共有约数中最大的一个。也称最大公因数、最大公因子，a， b的最大公约数记为（a，b），同样的，a，b，c的最大 公约数记为（a，b，c），多个 整数的最大公约数也有同样的记号。求最大公约数有多种 方法，常见的有 质因数分解法、 短除法、 辗转相除法、 更相减损法。</p>
<h4 id="辗转相减法求最大公约数" tabindex="-1"><a class="header-anchor" href="#辗转相减法求最大公约数"><span>辗转相减法求最大公约数</span></a></h4>
<p>用(a，b)表示a和b的最大公因数：有结论(a，b)=(a，ka+b)，其中a、b、k都为自然数。</p>
<p>也就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数，其公约数不变，比如(4，6)=(4+6，6)=(4，6+2×4)=2.</p>
<p>要证明这个原理很容易：如果p是a和ka+b的公约数，p整除a，也能整除ka+b.那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的.</p>
<p>基于上面的原理，就能实现我们的迭代相减法：(78，14)=(64，14)=(50，14)=(36，14)=(22，14)=(8，14)=(8，6)=(2，6)=(2，4)=(2，2)=(0，2)=2</p>
<p>基本上思路就是大数减去小数，一直减到能算出来为止，在作为练习的时候，往往进行到某一步就已经可以看出得值.</p>
<h4 id="辗转相减到辗转相除" tabindex="-1"><a class="header-anchor" href="#辗转相减到辗转相除"><span>辗转相减到辗转相除</span></a></h4>
<p>迭代相减法简单，不过步数比较多，实际上我们可以看到，在上面的过程中，由(78，14)到(8，14)完全可以一步到位，因为(78，14)=(14×5+8，14)=(8，14)，由此就诞生出我们的辗转相除法.</p>
<p>即：(a， b) = (a % b， b) = （b, a %b）</p>
<p>相当于每一步都把数字进行缩小，等式右边就是每一步对应的缩小结果。</p>
<p>对（a， b）连续使用辗转相除，直到小括号内右边数字为0，小括号内左边的数就是两数最大公约数。</p>
<h3 id="参考代码-3" tabindex="-1"><a class="header-anchor" href="#参考代码-3"><span>参考代码</span></a></h3>
<div class="language-c++ line-numbers-mode" data-highlighter="shiki" data-ext="c++" style="background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379">&#x3C;iostream></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> n;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">n;</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF">(n</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">        int</span><span style="color:#ABB2BF"> a, b;cin </span><span style="color:#C678DD">>></span><span style="color:#ABB2BF"> a </span><span style="color:#C678DD">>></span><span style="color:#ABB2BF"> b; </span></span>
<span class="line"><span style="color:#C678DD">        while</span><span style="color:#ABB2BF">(b){</span></span>
<span class="line"><span style="color:#C678DD">            int</span><span style="color:#ABB2BF"> c </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> a </span><span style="color:#C678DD">%</span><span style="color:#ABB2BF"> b;</span></span>
<span class="line"><span style="color:#ABB2BF">            a </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> b;</span></span>
<span class="line"><span style="color:#ABB2BF">            b </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> c;</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span></span>
<span class="line"><span style="color:#ABB2BF">        cout </span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF"> a </span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF"> endl;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>聊胜于无的优化</p>
<p>对于(a, b)，如果 a % b == 0， 则b就是最大公约数，可以提前结束循环。</p>
<div class="language-c++ line-numbers-mode has-collapsed-lines collapsed" data-highlighter="shiki" data-ext="c++" style="--vp-collapsed-lines:15;background-color:#282c34;color:#abb2bf"><pre class="shiki one-dark-pro vp-code" v-pre=""><code><span class="line"><span style="color:#C678DD">#include</span><span style="color:#98C379">&#x3C;iostream></span></span>
<span class="line"><span style="color:#C678DD">using</span><span style="color:#C678DD"> namespace</span><span style="color:#E5C07B"> std</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#C678DD">int</span><span style="color:#61AFEF"> main</span><span style="color:#ABB2BF">(){</span></span>
<span class="line"><span style="color:#C678DD">    int</span><span style="color:#ABB2BF"> n;cin</span><span style="color:#C678DD">>></span><span style="color:#ABB2BF">n;</span></span>
<span class="line"><span style="color:#C678DD">    while</span><span style="color:#ABB2BF">(n</span><span style="color:#C678DD">--</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#C678DD">        int</span><span style="color:#ABB2BF"> a, b;cin </span><span style="color:#C678DD">>></span><span style="color:#ABB2BF"> a </span><span style="color:#C678DD">>></span><span style="color:#ABB2BF"> b;</span></span>
<span class="line"><span style="color:#C678DD">        if</span><span style="color:#ABB2BF">(a </span><span style="color:#C678DD">%</span><span style="color:#ABB2BF"> b </span><span style="color:#C678DD">==</span><span style="color:#D19A66"> 0</span><span style="color:#ABB2BF">){</span></span>
<span class="line"><span style="color:#ABB2BF">        	cout</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">b</span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF">endl;</span></span>
<span class="line"><span style="color:#C678DD">        	continue</span><span style="color:#ABB2BF">;</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span></span>
<span class="line"><span style="color:#C678DD">        while</span><span style="color:#ABB2BF">(b){</span></span>
<span class="line"><span style="color:#C678DD">            int</span><span style="color:#ABB2BF"> c </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> a </span><span style="color:#C678DD">%</span><span style="color:#ABB2BF"> b;</span></span>
<span class="line"><span style="color:#ABB2BF">            a </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> b;</span></span>
<span class="line"><span style="color:#ABB2BF">            b </span><span style="color:#C678DD">=</span><span style="color:#ABB2BF"> c;</span></span>
<span class="line"><span style="color:#ABB2BF">        }</span></span>
<span class="line"><span style="color:#ABB2BF">        cout </span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF"> a </span><span style="color:#C678DD">&#x3C;&#x3C;</span><span style="color:#ABB2BF"> endl;</span></span>
<span class="line"><span style="color:#ABB2BF">    }</span></span>
<span class="line"><span style="color:#ABB2BF">}</span></span></code></pre>
<div class="line-numbers" aria-hidden="true" style="counter-reset:line-number 0"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div><div class="collapsed-lines"></div></div></div></template>


